class HuffmanTree:
    def __init__(self, n, data):
        self.n = n  # 叶子节点个数
        self.ht = [None] * (2 * n)  # 哈夫曼树节点列表，长度为2n-1，初始化为None
        self.hc = [None] * (n + 1)  # 哈夫曼编码列表，长度为n+1，初始化为None
        for i in range(len(self.ht)):
            self.ht[i] = Node()  # 初始化每个节点对象

    def select(self, end_index):
        min = self.ht[1].weight  # 找到最小权值
        s1 = 1  # 更新s1的值
        temp = self.ht[s1].weight  # 将原值存放起来，然后先赋予最大值，防止s1被重复选择
        self.ht[s1].weight = float('inf')
        min = float('inf')
        for i in range(1, end_index + 1):  # 从1至i-1中个结点中顺序查找出权值最小的结点
            if self.ht[i].weight < min and self.ht[i].parent == 0:  # 找到最小权值
                min = self.ht[i].weight  # 更新min的大小
                s2 = i  # 更新s2的值
        self.ht[s1].weight = temp  # 恢复原来的值
        return s1, s2

    def create_huffmantree(self):
        # 构造哈夫曼树
        if self.n <= 1:
            return
        m = 2 * self.n - 1
        for i in range(1, self.n + 1):  # 输入前n个单元中叶子结点的权值
            self.ht[i].weight = data[i - 1]
        for i in range(self.n + 1, m + 1):  # 通过n-1次的选择、删除、合并来创建哈夫曼树
            s1, s2 = self.select(i - 1)  # 在ht[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,并返回它们在ht中的序号s1和s2
            self.ht[s1].parent = i
            self.ht[s2].parent = i  # 得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
            self.ht[i].lchild = s1
            self.ht[i].rchild = s2  # s1,s2分别作为i的左右孩子
            self.ht[i].weight = self.ht[s1].weight + self.ht[s2].weight  # i的权值为左右孩子权值之和

    def create_huffmancode(self):
        # 从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表hc中
        cd = [' ' for _ in range(0, self.n - 1)]  # 分配临时存放每个字符编码的动态数组空间
        for i in range(1, self.n + 1):  # 逐个字符求哈夫曼编码
            start = self.n - 1  # start开始时指向最后，即编码结束符位置
            c = i
            f = self.ht[i].parent  # f指向结点c的双亲结点
            while f != 0:
                start -= 1  # 回溯一次start向前指一个位置
                if self.ht[f].lchild == c:
                    cd[start] = '0'  # 结点c是f的左孩子，则生成代码0
                else:
                    cd[start] = '1'  # 结点c是f的右孩子，则生成代码1
                c = f
                f = self.ht[f].parent  # 继续向上回溯
            self.hc[i] = ''.join(cd[start:])  # 为第i个字符编码分配空间

    def print_huffmantree(self):
        # 输出哈夫曼树状态表
        print("结点 i weight parent lchild rchild")
        for i in range(1, 2 * self.n):
            print(" {0} {1} {2} {3} {4}".format(i, self.ht[i].weight, self.ht[i].parent, self.ht[i].lchild,
                                                self.ht[i].rchild))

    def print_haffmancode(self):
        # 输出哈夫曼编码
        for i in range(1, self.n + 1):
            print(self.ht[i].weight, "编码为:", self.hc[i])


class Node:
    def __init__(self):
        self.weight = 0
        self.parent = 0
        self.lchild = 0
        self.rchild = 0


if __name__ == "__main__":
    data = [5, 29, 7, 8, 14, 23, 3, 11]
    ht = HuffmanTree(8, data)
    print("ht的初态为：")
    ht.print_huffmantree()
    ht.create_huffmantree()
    print("ht的终态为：")
    ht.print_huffmantree()
    ht.create_huffmancode()
    print('哈夫曼编码为：')
    ht.print_haffmancode()
